import java.util.ArrayList;

public class GraphByNode {
    //邻接表实现图
    static class Node{
        public int src;
        public int dest;
        public int weight;
        public Node  next;
        public Node(int src,int dest,int weight){
            this.src=src;
            this.dest=dest;
            this.weight=weight;
        }
    }

    public char[] arrayV;//顶点集合,字符
    public ArrayList<Node> edgList;//存储边，边为node类型
    public boolean isDirect;//是否是有向图
    public GraphByNode(int size,boolean isDirect){
        this.arrayV=new char[size];
        edgList=new ArrayList<>(size);
        for (int i=0;i<size;i++){
            edgList.add(null);
        }
        this.isDirect=isDirect;

    }
    //初始化顶点数组
    public void initArrayV(char[] array){
        for (int i=0;i< array.length;i++){
            arrayV[i]=array[i];
        }
    }
    //获取元素下标
    private int getIndexOfV(char v){
        for (int i = 0; i < arrayV.length; i++) {
            if (arrayV[i]==v){
                return i;
            }
        }
        return -1;
    }
    //添加边
    public void addEdge(char srcv,char destv,int weight){
        int srcIndex=getIndexOfV(srcv);//获取下标
        int destIndex=getIndexOfV(destv);//获取下标
        addEdgeChild(srcIndex,destIndex,weight);
        if(!isDirect){
            addEdgeChild(destIndex,srcIndex,weight);
        }
    }
    private void addEdgeChild(int srcIndex,int destIndex,int weight){
        Node cur=edgList.get(srcIndex);//获取顶点srcv对应的边链表的头节点cur
        while (cur!=null){//如果已经存在从顶点srcv到顶点destv的边，则直接返回；否则，继续向后遍历。
            if (cur.dest==destIndex){//以出度表判断
                return;
            }
            //cur.dest!=destIndex,cur一直往链表后面走
            cur=cur.next;
        }
        //之前没有存储的边
        //如果遍历到链表末尾仍未找到对应的边，则新建一个表示从顶点 srcv 到顶点 destv 权重为 weight 的边节点 node
        Node node =new Node(srcIndex,destIndex,weight);//新建边节点
        //将新建的边节点 node 插入到顶点 srcv 对应的边链表的头部，并更新邻接表中该顶点对应的边链表的头节点信息，
        // 即调用 edgList.set(srcIndex, node) 方法将原本的头节点替换为 node
        node.next=edgList.get(srcIndex);//edgList.get(srcIndex)，取出 edgList 中索引为 srcIndex 的元素（即 Node 对象），并将其赋值给 node.next
        edgList.set(srcIndex,node);//将指定位置 index 的元素替换为 node
    }

}
